package oj;

//根据二叉树创建字符串：给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
//空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
public class Solution_606 {
    //要将二叉树转换为字符串输出，但是因为 String 具有不可变性所以要使用 StringBuilder 类
    public String tree2str(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        preorder(root,sb);
        //得到了前序遍历的结果
        //删除第一个字符 ’(‘ 和最后一个字符 ’)‘
        sb.deleteCharAt(0);     //下标为 0 的字符就是 ’(‘
        sb.deleteCharAt(sb.length() - 1);       //sb.length() - 1 是最后一个元素的下标，删除最后一个元素，即 ')'
        return sb.toString();
    }
    //思路：根据观察，返回的字符串
    // 1.每一层都有()
    //2.当当前结点没有右子树时是 (2(4)),右子树为空时 ()不显示
    //3.左子树为空是 () 显示
    //4.第一层的 () 不显示
    public void preorder(TreeNode root, StringBuilder sb){
        if(root == null){
            sb.append("()");    //代表是空树，在sb中添加()
            return;
        }
        //在判断之前先加一个左括号
        sb.append('(');
        if(root.left == null && root.right == null){
            //只有一个根结点
            sb.append(root.val);    //不走左右子树
        }else if(root.left == null && root.right != null){
            //左为空，右不为空
            sb.append(root.val);
            preorder(root.left,sb);
            preorder(root.right,sb);
        }else if(root.left != null && root.right == null){
            //左不为空，右为空
            sb.append(root.val);
            preorder(root.left,sb);     //不走右子树了
        }else{
            //左右子树都不为空
            sb.append(root.val);
            preorder(root.left,sb);
            preorder(root.right,sb);
        }
        sb.append(')');
    }
}
